home *** CD-ROM | disk | FTP | other *** search
/ SGI Freeware 1999 August / SGI Freeware 1999 August.iso / dist / samba.idb / usr / samba / src / source / ubiqx / ubi_StackQueue.c.z / ubi_StackQueue.c
Encoding:
C/C++ Source or Header  |  1998-10-28  |  5.6 KB  |  150 lines
  1. /* ========================================================================== **
  2.  *                              ubi_StackQueue.c
  3.  *
  4.  *  Copyright (C) 1997 by Christopher R. Hertel
  5.  *
  6.  *  Email: crh@ubiqx.mn.org
  7.  * -------------------------------------------------------------------------- **
  8.  *  This module implements simple queues and stacks using a singly linked
  9.  *  list.
  10.  * -------------------------------------------------------------------------- **
  11.  *
  12.  *  This library is free software; you can redistribute it and/or
  13.  *  modify it under the terms of the GNU Library General Public
  14.  *  License as published by the Free Software Foundation; either
  15.  *  version 2 of the License, or (at your option) any later version.
  16.  *
  17.  *  This library is distributed in the hope that it will be useful,
  18.  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  19.  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  20.  *  Library General Public License for more details.
  21.  *
  22.  *  You should have received a copy of the GNU Library General Public
  23.  *  License along with this library; if not, write to the Free
  24.  *  Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  25.  *
  26.  * -------------------------------------------------------------------------- **
  27.  *  This module uses a singly-linked list to implement both a queue and a
  28.  *  stack.  For a queue, entries are added at the tail and removed from the
  29.  *  head of the list.  For a stack, the entries are entered and removed from
  30.  *  the head of the list. A traversal of the list will always start at the
  31.  *  head of the list and proceed toward the tail.  This is all mind-numbingly
  32.  *  simple, but I'm surprised by the number of programs out there which
  33.  *  re-implement this a dozen or so times.
  34.  *
  35.  *  Note:  When the list header is initialized, the Tail pointer is set to
  36.  *         point to the Head pointer.  This simplifies the InsTail function
  37.  *         at little or no cost to InsHead or Remove.  The one problem is
  38.  *         that you can't initialize a stack or queue headerby simply zeroing
  39.  *         it out.  One sure way to initialize the header is to call
  40.  *         ubi_sqInit().  Another option would be something like this:
  41.  *
  42.  *         static ubi_sqList MyList = { NULL, (ubi_sqNodePtr)&MyList, 0 };
  43.  *
  44.  *         See ubi_sqInit() and the ubi_sqList structure for more info.
  45.  *
  46.  * -------------------------------------------------------------------------- **
  47.  *
  48.  * Revision 0.1  1997/10/24 02:47:52  crh
  49.  * Initial revision.
  50.  *
  51.  * ========================================================================== **
  52.  */
  53.  
  54. #include "ubi_StackQueue.h"
  55.  
  56. /* ========================================================================== **
  57.  * Functions...
  58.  */
  59.  
  60. ubi_sqListPtr ubi_sqInit( ubi_sqListPtr ListPtr )
  61.   /* ------------------------------------------------------------------------ **
  62.    * Initialize a stack & queue header.
  63.    *
  64.    *  Input:  ListPtr - A pointer to the list header that is to be
  65.    *                    initialized for use.
  66.    *
  67.    *  Output: A pointer to the initialized list header (i.e., same as
  68.    *          <ListPtr>).
  69.    *
  70.    * ------------------------------------------------------------------------ **
  71.    */
  72.   {
  73.   ListPtr->Head  = NULL;
  74.   ListPtr->Tail  = (ubi_sqNodePtr)ListPtr;
  75.   ListPtr->count = 0;
  76.   return( ListPtr );
  77.   } /* ubi_sqInit */
  78.  
  79. ubi_sqNodePtr ubi_sqInsHead( ubi_sqListPtr ListPtr, ubi_sqNodePtr New )
  80.   /* ------------------------------------------------------------------------ **
  81.    * Insert a new node at the head of the list (push).
  82.    *
  83.    *  Input:  ListPtr - A pointer to the stack into which the node is to
  84.    *                    be inserted.
  85.    *          New     - Pointer to the node that is to be pushed onto the
  86.    *                    stack.
  87.    *
  88.    *  Output: A pointer to the node that was added to the list (i.e., same
  89.    *          same as <New>).
  90.    *
  91.    * ------------------------------------------------------------------------ **
  92.    */
  93.   {
  94.   if( NULL == ListPtr->Head )   /* If list is empty, must change tail ptr. */
  95.     ListPtr->Tail = New;
  96.   New->Next     = ListPtr->Head;
  97.   ListPtr->Head = New;
  98.   ++(ListPtr->count);
  99.   return( New );
  100.   } /* ubi_sqInsHead */
  101.  
  102. ubi_sqNodePtr ubi_sqInsTail( ubi_sqListPtr ListPtr, ubi_sqNodePtr New )
  103.   /* ------------------------------------------------------------------------ **
  104.    * Add a new node to the tail of the list (enqueue).
  105.    *
  106.    *  Input:  ListPtr - A pointer to the queue into which the node is to
  107.    *                    be inserted.
  108.    *          New     - Pointer to the node that is to be enqueued.
  109.    *
  110.    *  Output: A pointer to the node that was inserted into the queue (i.e.,
  111.    *          the same as <New>).
  112.    *
  113.    * ------------------------------------------------------------------------ **
  114.    */
  115.   {
  116.   ListPtr->Tail->Next = New;
  117.   ListPtr->Tail       = New;
  118.   New->Next           = NULL;
  119.   ++(ListPtr->count);
  120.   return( New );
  121.   } /* ubi_sqInsTail */
  122.  
  123. ubi_sqNodePtr ubi_sqRemove( ubi_sqListPtr ListPtr )
  124.   /* ------------------------------------------------------------------------ **
  125.    * Remove the frontmost entry from the queue, or topmost entry from the
  126.    * stack.
  127.    *
  128.    *  Input:  ListPtr - A pointer to the list from which the node is to be
  129.    *                     removed.
  130.    *
  131.    *  Output: A pointer to the node that was removed.
  132.    *
  133.    * ------------------------------------------------------------------------ **
  134.    */
  135.   {
  136.   ubi_sqNodePtr Old = ListPtr->Head;
  137.  
  138.   if( NULL != Old )
  139.     {
  140.     if( NULL == Old->Next )
  141.       ListPtr->Tail = (ubi_sqNodePtr)ListPtr;
  142.     ListPtr->Head = Old->Next;
  143.     --(ListPtr->count);
  144.     }
  145.   return( Old );
  146.   } /* ubi_sqRemove */
  147.  
  148.  
  149. /* ================================ The End ================================= */
  150.